package com.lhcai.lc.other;

import java.util.HashMap;
import java.util.Map;


/**
 * @author lhcstart
 * @create 2023-02-26 16:05
 */

/**
 * 从中序与后序遍历序列构造二叉树
 */
public class lc106 {

    int post_idx;//后序遍历得到数组，最后一位的索引
    int[] post;//后序遍历数组
    int[] in;//中序遍历数组
    Map<Integer, Integer> map = new HashMap<>();//存放中序遍历的数据


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        in = inorder;
        post = postorder;
        // 从后序遍历的最后一个元素开始
        post_idx = postorder.length - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (int val : inorder) {
            map.put(val, idx++);
        }
        return helper(0, inorder.length - 1);

    }


    public TreeNode helper(int in_left, int in_right) {
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return null;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = post[post_idx];
        TreeNode root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        Integer index = map.get(root_val);

        // 下标减一
        post_idx--;
        // 构造右子树
        root.right = helper(index + 1, in_right);
        // 构造左子树
        root.left = helper(in_left, index - 1);
        return root;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
